% Copyright 2011-2012 David Hadka.  All Rights Reserved.
%
% This file is part of the MOEA Framework User Manual.
%
% Permission is granted to copy, distribute and/or modify this document under
% the terms of the GNU Free Documentation License, Version 1.3 or any later
% version published by the Free Software Foundation; with the Invariant Section
% being the section entitled "Preface", no Front-Cover Texts, and no Back-Cover
% Texts.  A copy of the license is included in the section entitled "GNU Free
% Documentation License".

\chapter{Advanced Topics}

\section{PISA Integration}
The Platform and Programming Language Independent Interface for Search Algorithms (PISA), available at \webpage{http://www.tik.ee.ethz.ch/pisa/}, is a language-neutral programming interface for creating search and optimization algorithms.  PISA specifies three components required for search algorithms:

\begin{enumerate}
  \item selectors, which define the optimization algorithms;
  \item variators, which define the optimization problems; and
  \item a communication scheme using plaintext files.
\end{enumerate}

This design offers several benefits.  First, it clearly demarcates the responsibilities of algorithm experts from those of application engineers.  The algorithm experts focus on designing and improving the behavior of optimization algorithms (i.e., selectors), whereas application engineers are responsible for encoding the details of their problem (i.e., variators).  Second, the file-based communication scheme employed by PISA permits selectors and variators to be written in nearly any programming language, which may be paired with a selector/variator written in a completely different language.  Third, the standardized communication scheme enables plug-and-play integration, allowing one module to be swapped out for another with little to no effort.  For instance, one selector may be replaced by another simply by changing which executable is run.

The fundamental drawback of PISA is a result of its reliance on a file-based communication scheme.  File access on modern computers remains a (relatively) slow operation, which is further exacerbated by the need to constantly poll the communication files for changes.  Nonetheless, PISA opens the door to a number of state-of-the-art optimization algorithms, including:

\begin{enumerate}
  \item Set Preference Algorithm for Multiobjective Optimization (SPAM)
  \item Sampling-Based Hypervolume-Oriented Algorithm (SHV)
  \item Simple Indicator-Based Evolutionary Algorithm (SIBEA)
  \item Hypervolume Estimation Algorithm for Multiobjective Optimization (HypE)
  \item Simple Evolutionary Multiobjective Optimizer (SEMO2)
  \item Fair Evolutionary Multiobjective Optimizer (FEMO)
  \item Strength Pareto Evolutionary Algorithm 2 (SPEA2)
  \item Nondominated Sorting Genetic Algorithm 2 (NSGA2)
  \item Epsilon-Constraint Evolutionary Algorithm (ECEA)
  \item Indicator-Based Evolutionary Algorithm (IBEA)
  \item Multiple Single Objective Pareto Sampling (MSOPS)
  \item Epsilon-Dominance MOEA ($\epsilon$-MOEA)
\end{enumerate}

For this reason, the MOEA Framework provides the support necessary to integrate with the PISA library.  The \class{PISAAlgorithm} class acts as a variator, which knows how to communicate with a PISA selector using the file-based communication protocol.

\subsection{Adding a PISA Selector}
A standardized method for adding PISA selectors to the MOEA Framework is provided.  The steps required to add a new PISA selector are:

\begin{enumerate}
  \item Download and extract a PISA selector
  \item Edit \file{global.properties}
    \begin{enumerate}
      \item Add the name of the selector, \plaintext{NAME}, to the comma-separated list of available PISA selectors in \plaintext{org.moeaframework.algorithm.pisa.algorithms}
      \item Add the property \plaintext{org.moeaframework.algorithm.pisa.NAME.command}, which points to the program executable which starts the PISA selector
      \item Add the property \plaintext{org.moeaframework.algorithm.pisa.NAME.configuration},  which points to the configuration file for the PISA selector
    \end{enumerate}
\end{enumerate}

For example, if we install the SEMO2 selector, we would first download the SEMO2 binaries from \webpage{http://www.tik.ee.ethz.ch/pisa/}.  These binaries are typically packaged as a compressed file (.zip or .tar.gz).  Next, extract the contents of this compressed file into the MOEA Framework installation folder.  In this example, we extracted the contents to the folder \folder{pisa/SEMO2}.  Finally, add the following three lines to the \file{global.properties} file:

\begin{lstlisting}[language=Plaintext]
org.moeaframework.algorithm.pisa.algorithms=SEMO2
org.moeaframework.algorithm.pisa.SEMO2.command=./pisa/SEMO2/semo2.exe
org.moeaframework.algorithm.pisa.SEMO2.configuration=./pisa/SEMO2/semo2_params.txt
\end{lstlisting}

Once completed, you should be able to run the diagnostic tool and confirm that SEMO2 appears in the list of available algorithms.  Additionally, SEMO2 may be referenced throughout the MOEA Framework wherever the algorithm is specified as a string, such as:

\begin{lstlisting}[language=Java]
new Executor()
		.withProblem("Kursawe")
		.withAlgorithm("SEMO2")
		.withMaxEvaluations(10000)
		.run();
\end{lstlisting}

\subsection{Troubleshooting}

\noindent
\textit{I'm attempting to run the PISA algorithm, but nothing is happening.  The task manager shows the PISA executable is running, but shows 0\% CPU usage.}

\begin{quote}
The MOEA Framework uses your system's default temporary directory as the location of the files used to communicate with the PISA selector.  Some PISA selectors do not support paths containing spaces, and the path to the default temporary directory on older versions of Windows contains spaces.  This causes a miscommunication between the MOEA Framework and PISA, which generally causes the MOEA Framework and PISA executables to stall.

The easiest workaround is to override the temporary directory location so that the space is removed.  This can be accomplished by editing the \file{global.properties} file and adding the line:

\begin{lstlisting}[language=Plaintext]
java.io.tmpdir = C:/temp/
\end{lstlisting}
\end{quote}

\noindent
\textit{PISA runs fine for a while, but eventually crashes with the message ``Assertion failed: fp != null''.}

\begin{quote}
Some antivirus software is known to interfere with the file-based communication protocol used by PISA.  Antivirus programs which actively monitor files for changes may lock the file during a scan, potentially blocking access by the PISA selector.  Most PISA selectors will crash with the obscure message ``Assertion failed: fp != null''.

To verify this as the cause, you may temporarily disable your antivirus software and re-run the program.  Once verified, a permanent solution involves adding an exception to the antivirus software to prevent scanning the PISA communication files.  To implement this solution, first define the location of temporary files by adding the following line to the global.properties file:

\begin{lstlisting}[language=Plaintext]
java.io.tmpdir = C:/temp/
\end{lstlisting}

Then add an exception to your antivirus software to disable scanning files located in this directory.

(Note: Disabling an antivirus program from scanning a folder will leave its contents unprotected.  Follow these steps at your own risk.)
\end{quote}

\subsection{Customization}
As mentioned in troubleshooting, it is possible to change the location where the temporary files used to communicate with the PISA process are stored on your computer.

Part of the PISA communication involves transferring state between the MOEA Framework and the PISA executable.  In order to detect when the state changes, both the MOEA Framework and the PISA executable must periodically poll the current state.  A faster poll rate will improve the runtime performance of PISA, but will also increase the load placed on your computer's filesystem (as the state value is saved to and read from a plaintext file).  The poll rate, in milliseconds, can be controlled with the following property:

\begin{lstlisting}[language=Plaintext]
org.moeaframework.algorithm.pisa.poll = 100
\end{lstlisting}

\section{Configuring Hypervolume Calculation}
The hypervolume calculation is an important tool when comparing the performance of MOEAs.  This section details the available configuration options for the hypervolume calculation.

The hypervolume calculation computes the volume of the space dominated between the Pareto front and the nadir point.  The nadir point is set to the extremal objective values of the reference set plus some delta.  A non-zero delta is necessary to ensure such extremal values contribute a non-zero volume.  This delta is configurable by adding the following line to \file{global.properties}:

\begin{lstlisting}[language=Plaintext]
org.moeaframework.core.indicator.hypervolume_delta = 0.01
\end{lstlisting}

The hypervolume calculation is computationally expensive.  Use of the built-in hypervolume calculator may become prohibitive on Pareto fronts with $4$ or more objectives.  For this reason, it may be beneficial to use third-party hypervolume calculators instead.  A number of researchers have released C/C++ implementations of high-performance hypervolume calculators, including those listed below.

\begin{itemize}
  \item \webpage{http://ls11-www.cs.uni-dortmund.de/rudolph/hypervolume/start}
  \item \webpage{http://iridia.ulb.ac.be/~manuel/hypervolume/}
  \item \webpage{http://www.wfg.csse.uwa.edu.au/hypervolume/}\footnote{Some source code editing is necessary to modify the input and output format to be compatible with the MOEA Framework.}
\end{itemize}

Such hypervolume calculators can be used by the MOEA Framework by following two steps.  First, download and compile the desired hypervolume code.  This should result in an executable file, such as \file{hyp.exe}.  Second, configure the MOEA Framework to use this executable by adding a line similar to the following to the \file{global.properties} file.

\begin{lstlisting}[language=Plaintext]
org.moeaframework.core.indicator.hypervolume = hyp.exe {0} {1} {2} {3}
\end{lstlisting}

This property is specifying the executable and any required arguments.  The arguments are configurable by using the appropriate variable, such as \{0\}.  The complete list of available variables are shown in the table below.

\begin{center}
\begin{tabular}{ll}
  Variable & Description \\
  \hline
  \{0\} & Number of objectives \\
  \{1\} & Approximation set size \\
  \{2\} & File containing the approximation set \\
  \{3\} & File containing the reference point \\
  \{4\} & The reference point, separated by spaces
\end{tabular}
\end{center}

If all else fails, the hypervolume calculation can be disabled.  When disabled, the hypervolume will be reported as \java{NaN}.  To disable all hypervolume calculations, add the following line to \file{global.properties}:

\begin{lstlisting}[language=Plaintext]
org.moeaframework.core.indicator.hypervolume_enabled = false
\end{lstlisting}

\section{Storing Large Datasets}
When dealing with large datasets, proper data organization and management is key to avoiding headaches.  A number of tools are provided by the MOEA Framework for storing and manipulating large datasets.  The two key classes are the \java{ResultFileWriter} and \java{ResultFileReader}.  A result file is a collection of one or more approximation sets.  Each entry in the result file is the approximation set, including the decision variables and objectives for all solutions in the approximation set, and any additiona metadata you provide.  Note that this approximation set does not contain any constraints, as only feasible solutions are written in a result file.

\subsection{Writing Result Files}

The \java{ResultFileWriter} class is used to write result files.  The example code below demonstrates running the UF1 problem and recording the approximation set at each generation.  In addition, two pieces of metadata are stored: the current number of objective function evaluations (NFE) and the elapsed time.

\begin{lstlisting}[language=Java]
Problem problem = null;
Algorithm algorithm = null;
ResultFileWriter writer = null;
long startTime = System.currentTimeMillis();

try {
  problem = ProblemFactory.getInstance().getProblem("UF1");  
  algorithm = AlgorithmFactory.getInstance().getAlgorithm(
      "NSGAII", new Properties(), problem);

  try {
    writer = new ResultFileWriter(problem, new File("result.set"));

    //run the algorithm
    while (!algorithm.isTerminated() && 
        (algorithm.getNumberOfEvaluations() < 10000)) {
      algorithm.step(); //run one generation of the algorithm
    
      TypedProperties properties = new TypedProperties();
      properties.setInt("NFE", algorithm.getNumberOfEvaluations());
      properties.setLong("ElapsedTime", System.currentTimeMillis()-start);
      
      writer.append(new ResultEntry(algorithm.getResult(), properties));
    }
  } finally {
    //close the result file writer
    if (writer != null) {
      writer.close();
    }
  }
} finally {
  //close the problem to free any resources
  if (problem != null) {
    problem.close(); 
  }
}
\end{lstlisting}

\begin{important}
If the file you are saving already exists, the \java{ResultFileWriter} appends any new data to the end of the file.  If you do not want to append to any existing data, delete any old file first.
\end{important}

\subsection{Extract Information from Result Files}
The \java{ExtractData} command line utility is an extremely useful tool for extracting information from a result file.  It can extract any properties from the file as well as calculate specific performance indicators, and outputs this data in a clean, tabular format which can be read into spreadsheet software, such as LibreOffice Calc or Microsoft Excel.  When only extracting metadata, you need only specify the input file and the property keys to extract.  For instance, continuing the example from above, we can extract the \plaintext{NFE} and \plaintext{ElapsedTime} properties with the following command:

\begin{lstlisting}[language=Plaintext]
java org.moeaframework.analysis.sensitivity.ExtractData
    --problem UF1
    --input result.set
    NFE ElapsedTime
\end{lstlisting}

The output of this command will appear similar to:

\begin{lstlisting}[language=Plaintext]
#NFE ElapsedTime
100     125
200     156
300     172
400     187
500     203
...
\end{lstlisting}

Performance indicators can be calculated using one of the ``plus options.''  The options for the supported performance indicators include \plaintext{+hypervolume} for hypervolume, \plaintext{+generational} for generational distance, \plaintext{+inverted} for inverted generational distance, \plaintext{+epsilon} for additive $\epsilon$-indicator, \plaintext{+error} for maximum Pareto front error, \plaintext{+spacing} for spacing, and \plaintext{+contribution} for reference set contribution/coverage.  In addition, you must specify the problem, reference set, and optionally the $\epsilon$ values to use when calculating contribution.  For example:

\begin{lstlisting}[language=Plaintext]
java org.moeaframework.analysis.sensitivity.ExtractData
    --problem UF1
    --input result.set
    --reference ./pf/UF1.dat
    NFE ElapsedTime +hypervolume +epsilon +coverage
\end{lstlisting}

The added performance indicators will appear alongside the other properties:

\begin{lstlisting}[language=Plaintext]
#NFE ElapsedTime +hypervolume +epsilon +contribution
100     125          0.0      1.287951      0.0
200     156          0.0      1.149751      0.0
300     172          0.0      1.102796      0.0
400     187          0.0      1.083581      0.0
500     203          0.0      0.959353      0.0
...
\end{lstlisting}

Additional command line options allow you to format the output, such as removing the column header line or specifying the column separator character.

\section{Dealing with Maximized Objectives}
\label{sect:maximizing}
The MOEA Framework is setup to minimize objectives; it can not by itself maximize objectives.  This simplifies the program and increases its performance considerably.  By only allowing minimization objectives, the MOEA Framework can avoid the overhead of constantly determining the optimization direction whenever calculating the Pareto dominance relation.

This approach, however, puts the burden on the user to make the appropriate adjustments to their problem definition to allow maximization objectives.  The easiest way to allow maximization objectives is to negate the objective value, as demonstrated below:

\begin{lstlisting}[language=Java]
solution.setObjective(0, obj1);
solution.setObjective(1, -obj2); //negate the original objective value
\end{lstlisting}

By minimizing the negated objective value, we are maximizing the original objective value.  These negated objective values will be carried through to any output files produced by the MOEA Framework.  The help assist in managing these output files, version 1.13 includes the \java{Negater} command line utility.  The \java{Negater} tool processes any output file produced by the MOEA Framework and negates any specified objective.  For example, without the two objective example above, we can remove the negation in any output file with the following command.  Specifying a direction of 1 will negate the corresponding objective values in the processed file.

\begin{lstlisting}[language=Plaintext]
java org.moeaframework.analysis.sensitivity.Negater
    --direction 0,1
    output.set
\end{lstlisting}

\begin{important}
It is best to wait until all post-processing is complete before negating the objectives back to their original, maximized form as any calculations on the maximized form will be invalid.  You can always apply the \java{Negater} a second time to undo the change.  It is the responsibility of the user to manage their data files accordingly.
\end{important}